/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2025-08-17
 * Time: 17:12
 */
public class Test86 {

    public static int numSquares(int n) {
        int[] dp = new int[n+1];
        int INF = 0x3f3f3f3f, m = (int)Math.sqrt(n);
        for(int i = 1; i <= n; i++) {
            dp[i] = INF;
        }
        for(int i = 1; i <= m; i++) {
            for(int j = i*i; j <= n; j++) {
                dp[j] = Math.min(dp[j-i*i]+1,dp[j]);
            }
        }
        return dp[n];
    }



    public static void main(String[] args) {
        int n = 12;
        int ret = numSquares(n);
        System.out.println(ret);
    }
}
